
import java.util.Arrays;

import lombok.extern.slf4j.Slf4j;

/**
 * 字符串查找
 * @author zlzhangn
 */
@Slf4j
public class DataStructure_3_string {
	
	public static int bruteForceSearch(String source, String pattern){
		int index = -1;
		int i = 0;
		int j = 0;
		while(i<source.length() && (source.length()-i)>=(pattern.length()-j)){
			if(source.charAt(i) == pattern.charAt(j)){
				log.debug("匹配中：{}={}",source.charAt(i),pattern.charAt(j));
				if((j+1)==pattern.length()){
					log.debug("找到匹配字符串：起始位置{}",i-j);
					index = i-j;
					break;
				}
				i++;
				j++;
			}else{
				log.debug("{}！={}, i回溯到{}，j回溯到0",source.charAt(i),pattern.charAt(j),i-j+1);
				i=i-j+1;
				j=0;
			}
		}
		log.debug("{}",index==-1?"未匹配到字符串":"");
		return index;
	}
	
	public static int[] get_next(String str){
		char[] carr = str.toCharArray();
		int[] next = new int[carr.length];
		next[0] = -1;
		int i = 1;
		int j = 0;
		while(i<carr.length){
			if(j==-1){
				log.debug("i:{} j:{} [-1]查找最大公共前后缀-{}; next[{}]={}",i,j, Arrays.toString(Arrays.copyOf(carr, i+1)),i,j+1);
				next[i++]=0;
				j++;
			}else if(carr[i] == carr[j]){
				log.debug("i:{} j:{} 查找最大公共前后缀-{}; {}={}; next[{}]={}",i,j, Arrays.toString(Arrays.copyOf(carr, i+1)),carr[i],carr[j],i,j+1);
				next[i++] = ++j;
			}else{
				log.debug("i:{} j:{} 未查找公共前后缀-{}; {}!={}; j回溯到next[{}]={}",i,j,Arrays.toString(Arrays.copyOf(carr, i+1)),carr[i],carr[j],j,next[j]);
				j = next[j];
			}
		}
		log.debug("{}",Arrays.toString(next));
		return next;
	}
	/**kmp算法
	 * 主串：		aba|eabad
	 * 模式串：	aba|d
	 * 在第四位发现不匹配，已知aba公共前后缀是a，即匹配的部分只有a，所以中间的字符可以略过
	 * 			aba|eabad
	 * 			  a|bad
	 * @param source
	 * @param pattern
	 * @return
	 */
	public static int kmp(String source, String pattern){
		int[] next = get_next(pattern);
		int index = -1;
		char[] sourceStrArr = source.toCharArray();
		char[] patternStrArr = pattern.toCharArray();
		int j = 0;
		log.debug("开始在【{}】中寻找【{}】",source,pattern);
		for(int i=0; (source.length()-i)>=(pattern.length()-j);){
			if(j==-1 || sourceStrArr[i]==patternStrArr[j]){
				log.debug("i={};j={}, {}={}, i++ j++",i,j,sourceStrArr[i],j==-1?-1:patternStrArr[j]);
				if((j+1)==pattern.length()){
					index = i-j;
					break;
				}
				i++;
				j++;
			}else{
				log.debug("i={};j={}, {}!={}, j=next[{}]={}",i,j,sourceStrArr[i],patternStrArr[j],j,next[j]);
				j = next[j];
			}
		}
		log.debug("index={},{}",index,index!=-1?"匹配到":"未匹配到");
		return index;
	}
	
	public static void main(String[] args) {
		kmp("adsfasdfasdfasdfadadfasdfasdfasabaabcdf","abaabc");
		bruteForceSearch("adsfasdfasdfasdfadadfasdfasdfasabaabcdf","abaabc");
		
	}

}
